package com.love.twopoint;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class NSum {


    /**
     *
     * @param nums
     * @param n : 就是 n Sum
     * @param start 一般 start 都是从0开始，现在把他抽象出来，sums[start...end]
     * @param target
     * @return  NSum = i + (N-1)Sum
     */
    public static List<List<Integer>> nSumTarget(int[] nums,int n,int start,long target){
        Arrays.sort(nums);
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if(n < 2 || len < n){
            return res;
        }
        if(n == 2){
            int l = start;
            int r = nums.length - 1;
            while (l < r){
                int left = nums[l];
                int right = nums[r];
                int sum = left + right;

                if(sum > target){
                    while (l < r && nums[r] == right){
                        r--;
                    }
                }else if(sum < target){
                    while (l < r && nums[l] == left){
                        l++;
                    }
                }else {
                    List<Integer> rs = new ArrayList<>();
                    rs.add(left);
                    rs.add(right);
                    res.add(rs);
                    while (l < r && nums[l] == left){
                        l++;
                    }
                    while (l < r && nums[r] == right){
                        r--;
                    }
                }
            }
        }else {
            for (int i = start; i < len; i++) {

                List<List<Integer>> lists = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
                for (List<Integer> list : lists) {
                    list.add(nums[i]);
                    res.add(list);
                }
                while (i < len - 1 && nums[i] == nums[i+1]){
                    i++;
                }
            }

        }
        return res;
    }


    public static void main(String[] args) {
//        int[] nums = {1,0,-1,0,-2,2};

        int[] nums ={1000000000,1000000000,1000000000,1000000000};

        List<List<Integer>> lists = nSumTarget(nums, 4, 0, -294967296);
        for (List<Integer> list : lists) {

            System.out.println(Arrays.toString(list.toArray()));

        }
    }


}
